package leetcode.day;


import java.util.Arrays;

// 334. 递增的三元子序列
public class IncreasingTriplet {

    public static void main(String[] args) {
        int[] data = {1, 2, 3, 4};
        System.out.println(increasingTriplet2(data));
    }

    // 贪心
    public static boolean increasingTriplet(int[] nums) {
        if (nums.length < 3) {
            return false;
        }
        int first = nums[0], second = Integer.MAX_VALUE;
        for (int i = 1; i < nums.length; i++) {
            int x = nums[i];
            if (x > second) {
                return true;
            } else if (x > first) {
                second = x;
            } else {
                first = x;
            }
        }

        return false;
    }

    // dp+二分
    public static boolean increasingTriplet2(int[] nums) {
        int res = 0;
        int n = nums.length;
        int[] f = new int[n];
        for (int num : nums) {
            int low = 0;
            int high = res;
            while (low < high) {
                int mid = low + (high - low) / 2;
                if (f[mid] < num) {
                    low = mid + 1;
                } else {
                    high = mid;
                }
            }
            f[low] = num;
            if (res == high) {
                res++;
            }
        }
        return res >= 3;
    }

    public boolean increasingTriplet3(int[] nums) {
        int n = nums.length, ans = 1;
        int[] f = new int[n + 1];
        Arrays.fill(f, Integer.MAX_VALUE);
        for (int i = 0; i < n; i++) {
            int t = nums[i];
            int l = 1, r = i + 1;
            while (l < r) {
                int mid = (l + r) / 2;
                if (f[mid] >= t) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            f[r] = t;
            ans = Math.max(ans, r);
        }
        return ans >= 3;
    }

}
